package 算法基础模板.chapter_03;

import java.util.*;

/**
 * 图
 *
 * @author Summerday
 */
public class GraphTemplate {

    Map<Integer, List<Integer>> map = new HashMap<>();
    Queue<Integer> q = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();

    public static void main (String[] args) {
        GraphTemplate g = new GraphTemplate();
        g.add(1, 2);
        g.add(1, 3);
        g.add(2, 3);
        g.add(2, 4);

        //g.dfs(1);

    }

    // 添加一条边
    void add (int x, int y) {
        map.computeIfAbsent(x, o -> new ArrayList<>()).add(y);
    }

    void dfs (int u) {
        visited.add(u); // 标记一下走过了
        for (int e : map.getOrDefault(u, new ArrayList<>())) { // 遍历一下adj
            if (!visited.contains(e)) {
                dfs(e);
            }
        }
    }

    void bfs (int u) {
        q.add(u);
        visited.add(u);
        while (!q.isEmpty()) {
            int qq = q.poll();
            for (int e : map.getOrDefault(qq, new ArrayList<>())) {
                if (!visited.contains(e)) {
                    q.offer(e);
                }
            }
        }
    }


}
